/*

#include <iostream>
#include<string>
using namespace std;

int main()
{
    string s;
    int tmp = 0;
    while (cin >> s)
    {

        if (s.size() == 1)
        {
            cout << stoi(s)<< endl;
        }
        else
        {
            while (s.size() > 1)
            {
                tmp = 0;
                for (int i = s.size() - 1; i >= 0; i--)
                {
                    tmp += s[i] - '0';
                }
                s = to_string(tmp);
            }
            cout << tmp << endl;
        }
    }

    return 0;
}

#include<stdio.h>
#include <iostream>
#include <vector>
using namespace std;

int init(int n)
{
    vector<int>a = { 1, 1 };
    for (int i = 2; i <= n; i++)
    {
        a.push_back((a[i - 1] + a[i - 2]) % 10000);
    }
    return a[n];
}

int main()
{
    int sum, n;
    while (cin >> sum)
    {
        while (sum--)
        {
            cin >> n;
            int tmp = init(n);
            printf("%04d", tmp);
        }
        cout << endl;
    }
    return 0;

}

*/